{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Special Binary String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: makeLargestSpecial"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #特殊的二进制序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>特殊的二进制序列是具有以下两个性质的二进制序列：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>0 的数量与 1 的数量相等。</li>\n",
    "\t<li>二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给定一个特殊的二进制序列&nbsp;<code>S</code>，以字符串形式表示。定义一个<em>操作 </em>为首先选择&nbsp;<code>S</code>&nbsp;的两个连续且非空的特殊的子串，然后将它们交换。（两个子串为连续的当且仅当第一个子串的最后一个字符恰好为第二个子串的第一个字符的前一个字符。)</p>\n",
    "\n",
    "<p>在任意次数的操作之后，交换后的字符串按照字典序排列的最大的结果是什么？</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> S = &quot;11011000&quot;\n",
    "<strong>输出:</strong> &quot;11100100&quot;\n",
    "<strong>解释:</strong>\n",
    "将子串 &quot;10&quot; （在S[1]出现） 和 &quot;1100&quot; （在S[3]出现）进行交换。\n",
    "这是在进行若干次操作后按字典序排列最大的结果。\n",
    "</pre>\n",
    "\n",
    "<p><strong>说明:</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>S</code>&nbsp;的长度不超过&nbsp;<code>50</code>。</li>\n",
    "\t<li><code>S</code>&nbsp;保证为一个满足上述定义的<em>特殊 </em>的二进制序列。</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [special-binary-string](https://leetcode.cn/problems/special-binary-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [special-binary-string](https://leetcode.cn/problems/special-binary-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"11011000\"', '\"10\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeLargestSpecial(self, s: str) -> str:\n",
    "\n",
    "        def dfs(s):\n",
    "            w = ''\n",
    "            cur = 0\n",
    "            ans = []\n",
    "            for x in s:\n",
    "                if x == '1':\n",
    "                    cur += 1\n",
    "                else:\n",
    "                    cur -= 1\n",
    "                w += x\n",
    "                if cur == 0:\n",
    "                    ans.append('1' + dfs(w[1:-1]) +'0')\n",
    "                    w = ''\n",
    "            ans.sort(reverse=True)\n",
    "            return ''.join(ans)\n",
    "\n",
    "        return dfs(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeLargestSpecial(self, S: str) -> str:\n",
    "        count = i = 0\n",
    "        specials = []\n",
    "        for j, c in enumerate(S):\n",
    "            if c == '1':\n",
    "                count += 1\n",
    "            else:\n",
    "                count -= 1\n",
    "            if count == 0:\n",
    "                specials.append('1' + self.makeLargestSpecial(S[i+1:j]) + '0')\n",
    "                i = j + 1\n",
    "        return ''.join(sorted(specials, reverse=True))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeLargestSpecial(self, s: str) -> str:\n",
    "        if len(s) <= 2:\n",
    "            return s\n",
    "        cnt = left = 0\n",
    "        subs = []\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == \"1\":\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt -= 1\n",
    "                if cnt == 0:\n",
    "                    subs.append(\"1\" + self.makeLargestSpecial(s[left+1:i]) + \"0\")\n",
    "                    left = i + 1\n",
    "        subs.sort(reverse=True)\n",
    "        return \"\".join(subs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def makeLargestSpecial(self, s: str) -> str:\r\n",
    "        if len(s)<3:\r\n",
    "            return s\r\n",
    "        left=cnt=0\r\n",
    "        parts=[]\r\n",
    "        for i in range(len(s)):\r\n",
    "            if s[i]=='1':\r\n",
    "                cnt+=1\r\n",
    "            else:\r\n",
    "                cnt-=1\r\n",
    "                if cnt==0:\r\n",
    "                    parts.append('1'+self.makeLargestSpecial(s[left+1:i])+'0')\r\n",
    "                    left=i+1\r\n",
    "        parts.sort(reverse=True)\r\n",
    "        return ''.join(parts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeLargestSpecial(self, s: str) -> str:\n",
    "        cnt, start = 0, 0\n",
    "        mountain = []\n",
    "        for i, c in enumerate(s):\n",
    "            cnt += 2*int(c)-1\n",
    "            if cnt == 0:\n",
    "                mountain.append(\"1\" + self.makeLargestSpecial(s[start+1:i]) + \"0\")\n",
    "                start = i+1\n",
    "        return \"\".join(reversed(sorted(mountain)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeLargestSpecial(self, s: str) -> str:\n",
    "        one=0\n",
    "        two=0\n",
    "        ch=False\n",
    "        for i in range(len(s)):\n",
    "            #find the first substr\n",
    "            if s[i]==\"0\":\n",
    "                continue\n",
    "            s1=i\n",
    "            e1=i+1\n",
    "            one=1\n",
    "            \n",
    "            while e1<len(s):\n",
    "                if s[e1]==\"1\":\n",
    "                    one+=1\n",
    "                if s[e1]==\"0\":\n",
    "                    one-=1\n",
    "                e1+=1\n",
    "                if one==0:\n",
    "                    break\n",
    "                \n",
    "            if e1==len(s):\n",
    "                continue\n",
    "            if s[e1]==\"0\":\n",
    "                continue\n",
    "            two=1\n",
    "            s2=e1\n",
    "            e2=e1+1\n",
    "            while e2<len(s):\n",
    "                \n",
    "                if s[e2]==\"1\":\n",
    "                    two+=1\n",
    "                if s[e2]==\"0\":\n",
    "                    two-=1\n",
    "                e2+=1\n",
    "                if two==0:\n",
    "                    break\n",
    "            if two>0:\n",
    "                continue\n",
    "            #print(s[s1:e1],s[s2:e2],s[s1:e1]<s[s2:e2])\n",
    "            if s[s1:e1]<s[s2:e2]:\n",
    "                ch=True\n",
    "                s=s[:s1]+s[s2:e2]+s[s1:e1]+s[e2:]\n",
    "        if ch:\n",
    "            #print(\")))\")\n",
    "            return self.makeLargestSpecial(s)\n",
    "            \n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeLargestSpecial(self, s: str) -> str:\n",
    "        if len(s) <= 2:\n",
    "            return s\n",
    "        cnt = left = 0\n",
    "        subs = list()\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == \"1\":\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt -= 1\n",
    "                if cnt == 0:\n",
    "                    subs.append(\"1\" + self.makeLargestSpecial(s[left + 1 : i]) + \"0\")\n",
    "                    left = i + 1\n",
    "        subs.sort(reverse=True)\n",
    "        return \"\".join(subs)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeLargestSpecial(self, s: str) -> str:\n",
    "        if len(s) <= 2:\n",
    "            return s\n",
    "        \n",
    "        cnt = left = 0\n",
    "        subs = list()\n",
    "\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == \"1\":\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt -= 1\n",
    "                if cnt == 0:\n",
    "                    subs.append(\"1\" + self.makeLargestSpecial(s[left+1:i]) + \"0\")\n",
    "                    left = i + 1\n",
    "        \n",
    "        subs.sort(reverse=True)\n",
    "        return \"\".join(subs)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeLargestSpecial(self, s: str) -> str:\n",
    "        cnt = 0\n",
    "        # print(s)\n",
    "        if len(s) == 2: return '10'\n",
    "        ret = []\n",
    "        leftPtr = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c == '1':\n",
    "                cnt+=1\n",
    "            else:\n",
    "                cnt-=1\n",
    "            if cnt == 0:\n",
    "                # print(i, s[leftPtr+1:i])\n",
    "                ret.append('1'+self.makeLargestSpecial(s[leftPtr+1:i])+'0')\n",
    "                leftPtr = i+1\n",
    "        ret.sort(reverse=True)\n",
    "        return \"\".join(ret)\n",
    "\n",
    "\n",
    "        #find consecutive pairs of valid string\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeLargestSpecial(self, s: str) -> str:\n",
    "        #try every case\n",
    "        n=len(s)       \n",
    "        dfs=[s] \n",
    "        ans=s\n",
    "        while dfs:\n",
    "            \n",
    "            cs=dfs.pop()\n",
    "            # print(cs)\n",
    "            sd=defaultdict(list)\n",
    "            for i in range(n):\n",
    "                if cs[i]==\"1\":\n",
    "                    rich=1\n",
    "                    for j in range(i+1,n):\n",
    "                        if cs[j]==\"1\":\n",
    "                            rich+=1\n",
    "                        else:\n",
    "                            rich-=1\n",
    "                        if rich<0:                      \n",
    "                            break\n",
    "                        if rich==0:\n",
    "                            sd[i].append(j)\n",
    "            for start,ends in sd.items():\n",
    "                for end in ends:\n",
    "                    if end+1 in sd:\n",
    "                        for swi in sd[end+1]:\n",
    "                            news=cs[:start]+cs[end+1:swi+1]+cs[start:end+1]+cs[swi+1:]\n",
    "                            if news>ans:\n",
    "                                ans=news                            \n",
    "                                dfs.append(news)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeLargestSpecial(self, s: str) -> str:\n",
    "        count = i = 0\n",
    "        res = []\n",
    "        \n",
    "        # Find special substrings and recursively solve them\n",
    "        for j, c in enumerate(s):\n",
    "            count += 1 if c == '1' else -1\n",
    "            if count == 0:\n",
    "                res.append('1' + self.makeLargestSpecial(s[i + 1:j]) + '0')\n",
    "                i = j + 1\n",
    "        \n",
    "        # Sort the special substrings in reverse order to make the largest special string\n",
    "        return ''.join(sorted(res)[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeLargestSpecial(self, s: str) -> str:\n",
    "        if len(s) <= 2:\n",
    "            return s \n",
    "        n = len(s)\n",
    "        L = []\n",
    "        start = cnt = 0\n",
    "        for i, j in enumerate(s):\n",
    "            if j == '1':\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt -= 1\n",
    "                if cnt == 0:\n",
    "                    L.append('1' + self.makeLargestSpecial(s[start + 1: i]) + '0')\n",
    "                    start = i + 1\n",
    "        return ''.join(sorted(L, reverse=True))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeLargestSpecial(self, s: str) -> str:\n",
    "        # cur: 前缀和统计, last: 上一个特殊序列的结尾\n",
    "        cur = last = 0\n",
    "        # 所有可选的子特殊序列\n",
    "        candidates = []\n",
    "        for i, c in enumerate(s):\n",
    "            cur += 1 if c == '1' else -1\n",
    "            # 出现特殊序列, 一定是以1开头以0结尾\n",
    "            if not cur:\n",
    "                # 先将当前特殊序列排成最大, 首尾最终仍是1和0不可动，所以递归去掉头尾\n",
    "                candidates.append('1' + self.makeLargestSpecial(s[last + 1:i]) + '0')\n",
    "                last = i + 1\n",
    "        # 所有特殊子序列可以无限次交换，因此从大到小依次排列拼接即可\n",
    "        return \"\".join(sorted(candidates, reverse=True))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def isBracked(self, s: str) -> bool:\n",
    "        stk = []\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == \"1\":\n",
    "                stk.append(\"1\")\n",
    "            else:\n",
    "                assert len(stk) > 0\n",
    "                stk.pop()\n",
    "                if i < len(s) - 1 and len(stk) == 0:\n",
    "                    return False\n",
    "        return True\n",
    "        \n",
    "\n",
    "    def cutSortComp(self, s: str) -> str:\n",
    "        assert s[0] == \"1\" and s[-1] == \"0\"\n",
    "        bracked = self.isBracked(s)\n",
    "        cutted = s[1:len(s) - 1] if bracked else s\n",
    "        clips = []\n",
    "        one_cnt, zero_cnt, cur_s = 0, 0, \"\"\n",
    "        for i in range(len(cutted)):\n",
    "            if cutted[i] == \"1\":\n",
    "                one_cnt += 1\n",
    "            else:\n",
    "                zero_cnt += 1\n",
    "            cur_s += cutted[i]\n",
    "            if one_cnt == zero_cnt:\n",
    "                clips.append(cur_s)\n",
    "                cur_s = \"\"\n",
    "        for i in range(len(clips)):\n",
    "            clips[i] = self.cutSortComp(clips[i])\n",
    "        clips.sort()\n",
    "        clips.reverse()\n",
    "        # print(s, bracked, cutted, clips)\n",
    "        comp = functools.reduce(lambda x, y: x + y, clips) if len(clips) > 0 else \"\"\n",
    "        if bracked:\n",
    "            comp = \"1\" + comp + \"0\"\n",
    "        return comp\n",
    "\n",
    "    def makeLargestSpecial(self, s: str) -> str:\n",
    "        if s == \"\":\n",
    "            return \"\"\n",
    "        return self.cutSortComp(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeLargestSpecial(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        stack = []\n",
    "        cur = 0\n",
    "        pre = 0\n",
    "        for i in range(n):\n",
    "            if s[i] == '1':\n",
    "                cur += 1 \n",
    "            else:\n",
    "                cur -= 1 \n",
    "            if cur == 0:\n",
    "                stack.append('1' + self.makeLargestSpecial(s[pre + 1 : i]) + '0')\n",
    "                pre = i + 1 \n",
    "        return ''.join(sorted(stack, reverse = True))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cmp_to_key\n",
    "class Solution:\n",
    "    def makeLargestSpecial(self,s:str)->str:\n",
    "        lens=len(s)\n",
    "        def bigger(s1:str,s2:str)->int:\n",
    "            s12=s1+s2\n",
    "            s21=s2+s1\n",
    "            if s12<s21:\n",
    "                return 1\n",
    "            else:\n",
    "                return -1\n",
    "        def search(l,r)->str:\n",
    "            if l+2==r:\n",
    "                return '10'\n",
    "            p=l+1\n",
    "            nxl=l+1\n",
    "            cnt=0\n",
    "            tmp=[]\n",
    "            while p<r-1:\n",
    "                if s[p]=='1':\n",
    "                    cnt+=1\n",
    "                else:\n",
    "                    cnt-=1\n",
    "                p+=1\n",
    "                if cnt==0:\n",
    "                    tmp.append(search(nxl,p))\n",
    "                    nxl=p\n",
    "            tmp.sort(key=cmp_to_key(bigger))\n",
    "            tmps='1'\n",
    "            for i in tmp:\n",
    "                tmps+=i\n",
    "            tmps+='0'\n",
    "            #print(\"%d\\t%d\\t:%s\"%(l,r,tmps))\n",
    "            return tmps\n",
    "        ans=search(-1,lens+1)\n",
    "        return ans[1:lens+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeLargestSpecial(self, s: str) -> str:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        seen = {'': ''}\n",
    "        def func(s):\n",
    "            if s not in seen:\n",
    "                flag, sidx, arr = 0, 0, []\n",
    "                for eidx in range(len(s)):\n",
    "                    if s[eidx] == '1':\n",
    "                        flag += 1\n",
    "                    else:\n",
    "                        flag -= 1\n",
    "                    if not flag:\n",
    "                        if not sidx and eidx == len(s)-1:\n",
    "                            arr.append(s[0] + func(s[1:-1]) + s[-1])\n",
    "                        else:\n",
    "                            arr.append(func(s[sidx:eidx+1]))\n",
    "                        sidx = eidx + 1\n",
    "                arr.sort(reverse=True)\n",
    "                seen[s] = ''.join(arr)\n",
    "            return seen[s]\n",
    "        \n",
    "        return func(s)\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cmp_to_key, lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def makeLargestSpecial(self, s: str) -> str:\n",
    "        \"\"\"\n",
    "        :param s:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        def cmp1(a, b):\n",
    "            idx1 = min(len(a), len(b))\n",
    "            for i in range(idx1):\n",
    "                if a[i] < b[i]:\n",
    "                    return 1\n",
    "                if a[i] > b[i]:\n",
    "                    return -1\n",
    "            if len(a[idx1:]) == 0 and len(b[idx1:]) == 0:\n",
    "                return 0\n",
    "            if len(a[idx1:]) == 0:\n",
    "                return -1\n",
    "            return 1\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def get_ans(s1):\n",
    "            if len(s1) == 0:\n",
    "                return \"\"\n",
    "            if s1 == \"10\":\n",
    "                return s1\n",
    "            st1 = \"1\"\n",
    "            end1 = \"0\"\n",
    "            cnt = 0\n",
    "            anslist = []\n",
    "            prev = 0\n",
    "            for i in range(len(s1)):\n",
    "                if s1[i] == '1':\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    cnt -= 1\n",
    "                if cnt == 0:\n",
    "                    v1 = s1[prev+1:i]\n",
    "                    prev = i + 1\n",
    "                    ansx1 = st1 + get_ans(v1) + end1\n",
    "                    anslist.append(ansx1)\n",
    "            anslist.sort(key=cmp_to_key(cmp1))\n",
    "            mid1 = ''.join(anslist)\n",
    "            return mid1\n",
    "\n",
    "        ret = get_ans(s)\n",
    "        return ret\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cmp_to_key, lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def makeLargestSpecial(self, s: str) -> str:\n",
    "        \"\"\"\n",
    "\n",
    "        :param s:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "\n",
    "        def cmp1(a, b):\n",
    "            idx1 = min(len(a), len(b))\n",
    "            for i in range(idx1):\n",
    "                if a[i] < b[i]:\n",
    "                    return 1\n",
    "                if a[i] > b[i]:\n",
    "                    return -1\n",
    "            if len(a[idx1:]) == 0 and len(b[idx1:]) == 0:\n",
    "                return 0\n",
    "            if len(a[idx1:]) == 0:\n",
    "                return -1\n",
    "            return 1\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def get_ans(s1):\n",
    "            if len(s1) == 0:\n",
    "                return \"\"\n",
    "            if s1 == \"10\":\n",
    "                return s1\n",
    "\n",
    "            st1 = \"1\"\n",
    "            end1 = \"0\"\n",
    "\n",
    "            cnt = 0\n",
    "            anslist = []\n",
    "            prev = 0\n",
    "            for i in range(len(s1)):\n",
    "                if s1[i] == '1':\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    cnt -= 1\n",
    "                if cnt == 0:\n",
    "                    v1 = s1[prev+1:i]\n",
    "\n",
    "                    prev = i + 1\n",
    "                    ansx1 = st1 + get_ans(v1) + end1\n",
    "                    anslist.append(ansx1)\n",
    "            anslist.sort(key=cmp_to_key(cmp1))\n",
    "            mid1 = ''.join(anslist)\n",
    "            return mid1\n",
    "\n",
    "        ret = get_ans(s)\n",
    "        return ret\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
